package com.example.springboottest.example.sort;

/**
 * 直接插入排序，时间复杂度 O(n²)
 * 虽然交换的次数大于简单选择排序，但是循环的次数少于简单选择排序
 */
public class StraightInsertSort extends SortBase {
    public static void main(String[] args) {
        StraightInsertSort sort = new StraightInsertSort();
        sort.sort(sort.dataArr);
        sort.show(sort.dataArr);
    }

    @Override
    public void sort(int[] dataArr) {
        int swapCount = 0;
        int temp = 0;//临时变量
        for (int i = 1; i < dataArr.length; i++) {//从第二个数开始比较
            show(dataArr);
            temp = dataArr[i];  //将当前数插入到已经有序的数组中
            for (int j = i - 1; j >= 0; j--) {
                if (dataArr[j] > temp) {//如果前面的数大于当前数，交换
                    swapCount++;
                    swap(dataArr, j + 1, j);
                } else
                    break;   //如果前面的小于当前数，不用比较了
            }
        }
        System.out.println("直接插入排序完成，共进行\t" + swapCount + "次交换");
    }
}
